Flash memory devices are non-volatile data storage devices that can be electrically erased and reprogrammed. More generally, non-volatile memory (e.g., flash memory, as well as other types of non-volatile memory implemented using any of a variety of technologies) retains stored information even when not powered, as opposed to volatile memory, which requires power to maintain the stored information. Flash memories come in different capacities and electronic architectures. For example, depending on the manufacture, model, and technology used, memory banks in a flash memory device are arranged in blocks with sizes including but not limited to 16 KB, 128 KB, 256 KB, or 512 KB. Each block is further organized into pages. The number of pages can be 32, 64, 128, or more with each page having a possible size (but not limited to) of 256 B, 512 B, 1 KB, 2 KB, 4 KB, or 8 KB.
The data storage operations of flash memories typically comprise three basic operations: page read, page program (or equivalent to write), and block erase. Before a page can be programmed or re-programmed, a block erase of the block containing the page is performed first. Because of these data storage operation characteristics, a string of data is stored in physical memory locations in a flash memory device that do not correspond to the logical order of the data bits in the string of data. In order to locate the physical memory locations, software and hardware architectures of a flash memory device typically include a flash translation layer (FTL) that is responsible for translating logical addresses of data to and from physical memory addresses at which data are or will be stored in the flash memory device.
As capacity of flash memory devices increases, the dynamic random access memory (DRAM) required for storing the FTL mapping tables also increases, at corresponding increased cost. Furthermore, in typical usage, large portions of FTL mapping tables are mainly dormant for long periods of time.